import copy
from typing import List

sums = 0


def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
    path = []
    result = []

    def backtracking(start_index):
        global sums
        if sums == target:
            result.append(copy.copy(path))
            return
        if sums > target:
            return
        for i in range(start_index, len(candidates)):
            sums += candidates[i]
            path.append(candidates[i])
            backtracking(i)
            sums -= candidates[i]
            path.pop()

    backtracking(0)
    return result


if __name__ == '__main__':
    r = combinationSum(candidates=[2, 4, 6, 8], target=7)
    print(r)
